package edu.gmu.dglidde2.ece612.scheduler;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;

/**
 * The reference implementation of the {@link Scheduler} interface.
 * 
 * @author Doug Glidden
 */
public class SchedulerImpl implements Scheduler {

	private Set<String> processors = new HashSet<>();
	private Set<Task> tasks = new HashSet<>();

	// *********** BEGIN INTERNAL SCHEDULE GENERATION PROPERTIES *********** //

	// The following internal properties are used only during schedule
	// generation.
	private Schedule schedule;
	private long currentTime;
	private String currentProcessor;
	private long rollbackTime;
	private Set<Task> remainingTasks;
	private Set<Task> readyTasks;
	private Map<String, Long> firstReleaseTimes;
	private Map<String, LinkedList<Long>> processorAvailabilityTimes;

	// ************ END INTERNAL SCHEDULE GENERATION PROPERTIES ************ //

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * edu.gmu.dglidde2.ece612.scheduler.Scheduler#addProcessor(java.lang.String
	 * )
	 */
	@Override
	public void addProcessor(String processorName) {
		if (processorName == null) {
			throw new IllegalArgumentException("The processor name must not "
					+ "be null.");
		}
		if (processorName.isEmpty()) {
			throw new IllegalArgumentException("The processor name must not "
					+ "be an empty string.");
		}
		processors.add(processorName);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * edu.gmu.dglidde2.ece612.scheduler.Scheduler#addTask(edu.gmu.dglidde2.
	 * ece612.scheduler.Task)
	 */
	@Override
	public void addTask(Task task) {
		if (task == null) {
			throw new IllegalArgumentException("The task must not be null.");
		}
		if (!task.isValid()) {
			throw new IllegalArgumentException("The task must be a valid Task "
					+ "object.");
		}
		tasks.add(task);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.gmu.dglidde2.ece612.scheduler.Scheduler#generateSchedule()
	 */
	@Override
	public Schedule generateSchedule() throws MissingDataException,
			NoFeasibleScheduleException {
		validateInputs();

		initializeSchedulingProperties();
		while (!remainingTasks.isEmpty()) {
			while (currentProcessor != null) {
				rollbackTime = Long.MAX_VALUE;

				Task nextTask = chooseTaskToSchedule();
				while (!meetsDeadline(nextTask, currentTime)
						&& currentTime > nextTask.getPhase()) {
					attemptToMakeTaskMeetDeadline(nextTask);
				}
				schedule.addEntry(currentTime, currentProcessor, nextTask);

				updateSchedulingPropertiesForScheduledTask(nextTask);
			}
			if (!remainingTasks.isEmpty()) {
				updateSchedulingPropertiesForNoAvailableProcessor();
			}
		}

		return schedule;
	}

	/**
	 * Validates the inputs (processors and tasks) that have been provided.
	 * 
	 * This method is called prior to the beginning of schedule generation to
	 * ensure that all required inputs have been provided.
	 * 
	 * @throws MissingDataException
	 *             when missing data is detected, as defined by
	 *             {@link #validateProcessors()} and {@link #validateTasks()}.
	 */
	protected void validateInputs() throws MissingDataException {
		validateProcessors();
		validateTasks();
	}

	/**
	 * Validates that appropriate processors have been provided via the
	 * {@link #addProcessor(String)} method.
	 * 
	 * @throws MissingDataException
	 *             when no processors have been provideded.
	 */
	protected void validateProcessors() throws MissingDataException {
		if (processors.isEmpty()) {
			throw new MissingDataException("Cannot generate a schedule:  No "
					+ "processors.");
		}
	}

	/**
	 * Validates that appropriate tasks have been provided via the
	 * {@link #addTask(Task)} method.
	 * 
	 * @throws MissingDataException
	 *             when no tasks have been provided or when a task that was
	 *             provided specifies a processor that was not provided.
	 */
	protected void validateTasks() throws MissingDataException {
		if (tasks.isEmpty()) {
			throw new MissingDataException("Cannot generate a schedule:  No "
					+ "tasks.");
		}
		for (Task task : tasks) {
			if (task.getProcessorNames() != null) {
				if (!processors.containsAll(task.getProcessorNames())) {
					throw new MissingDataException("Cannot generate a "
							+ "schedule:  A task requests one or more "
							+ "processors which do not exist.");
				}
			}
		}
	}

	/**
	 * Initializes the internal properties used for scheduling.
	 * 
	 * This method is called at the beginning of schedule generation.
	 */
	protected void initializeSchedulingProperties() {
		initializeSchedule();
		initializeProcessorAvailabilityTimes();

		remainingTasks = generateNormalizedTaskSet();
		firstReleaseTimes = new HashMap<>();
		currentTime = findEarliestReleaseTime();
		rollbackTime = Long.MAX_VALUE;

		updateReadyTasks();
		chooseProcessor();
	}

	/**
	 * Updates the internal properties used for scheduling after successful
	 * scheduling of the provided task.
	 * 
	 * @param nextTask
	 *            the {@link Task} that was successfully scheduled.
	 * @throws NoFeasibleScheduleException
	 *             when the scheduled task's execution is found to prevent the
	 *             first task scheduled on the same processor in the following
	 *             period from starting at its scheduled time.
	 */
	protected void updateSchedulingPropertiesForScheduledTask(Task nextTask)
			throws NoFeasibleScheduleException {
		remainingTasks.remove(nextTask);
		readyTasks.remove(nextTask);
		if (firstReleaseTimes.get(currentProcessor) == null) {
			firstReleaseTimes.put(currentProcessor, currentTime);
		}

		long processorAvailabilityTime = currentTime
				+ nextTask.getExecutionTime();
		if (processorAvailabilityTime - schedule.getPeriod() > firstReleaseTimes
				.get(currentProcessor)) {
			throw new NoFeasibleScheduleException("Schedule exceeds "
					+ "the length of a hyperperiod.");
		}
		processorAvailabilityTimes.get(currentProcessor).push(
				processorAvailabilityTime);

		if (rollbackTime < Long.MAX_VALUE) {
			currentTime = rollbackTime;
			rollbackTime = Long.MAX_VALUE;
			updateReadyTasks();
		}
		chooseProcessor();
	}

	/**
	 * Updates the internal properties used for scheduling when no processor is
	 * found that is available and eligible to run at least one ready task.
	 */
	protected void updateSchedulingPropertiesForNoAvailableProcessor() {
		updateCurrentTime();
		updateReadyTasks();
		chooseProcessor();
	}

	/**
	 * Initializes the internal schedule property.
	 */
	protected void initializeSchedule() {
		schedule = new Schedule();
		schedule.setPeriod(calculateHyperperiod());
	}

	/**
	 * Initializes the internal property used to track the time when each
	 * processor next becomes available.
	 */
	protected void initializeProcessorAvailabilityTimes() {
		processorAvailabilityTimes = new HashMap<>();
		for (String processor : processors) {
			LinkedList<Long> times = new LinkedList<>();
			times.push(0L);
			processorAvailabilityTimes.put(processor, times);
		}
	}

	/**
	 * Updates the internal current scheduling time property to the next time
	 * when scheduling may occur (the earlier of the next time a processor
	 * becomes available and the next time a task is released).
	 */
	protected void updateCurrentTime() {
		long nextProcessorAvailabilityTime = findNextProcessorAvailabilityTime();
		long nextTaskReleaseTime = findNextReleaseTime();
		currentTime = Math.min(nextProcessorAvailabilityTime,
				nextTaskReleaseTime);
	}

	/**
	 * Updates internal property used to track the list of ready tasks available
	 * at the current scheduling time.
	 */
	protected void updateReadyTasks() {
		readyTasks = new HashSet<>();
		for (Task task : remainingTasks) {
			if (task.getPhase() <= currentTime) {
				readyTasks.add(task);
			}
		}
	}

	/**
	 * Calculates the hyperperiod of the provided tasks as the least common
	 * multiple of the tasks' periods.
	 * 
	 * @return the calculated hyperperiod.
	 */
	protected long calculateHyperperiod() {
		Iterator<Task> taskIterator = tasks.iterator();

		// Iteratively find LCM using reduction by GCD.
		BigInteger lcm = BigInteger.valueOf(taskIterator.next().getPeriod());
		while (taskIterator.hasNext()) {
			BigInteger nextPeriod = BigInteger.valueOf(taskIterator.next()
					.getPeriod());
			lcm = lcm.multiply(nextPeriod.divide(lcm.gcd(nextPeriod)));
		}

		return lcm.longValue();
	}

	/**
	 * Generates a set of tasks normalized to the period of the schedule from
	 * the provided tasks (i.e. a separate task is generated for each instance
	 * of each provided task within a single hyperperiod).
	 * 
	 * @return
	 */
	protected Set<Task> generateNormalizedTaskSet() {
		long hyperperiod = schedule.getPeriod();
		Set<Task> normalizedTaskSet = new HashSet<>();

		for (Task task : tasks) {
			for (int i = 0; i < hyperperiod / task.getPeriod(); i++) {
				Task normalizedTask = new Task();
				normalizedTask.setName(task.getName());
				normalizedTask.setPhase(task.getPhase() + i * task.getPeriod());
				normalizedTask.setPeriod(hyperperiod);
				normalizedTask.setExecutionTime(task.getExecutionTime());
				normalizedTask.setRelativeDeadline(task.getRelativeDeadline());
				if (task.getProcessorNames() != null) {
					normalizedTask.setProcessorNames(task.getProcessorNames());
				}
				normalizedTaskSet.add(normalizedTask);
			}
		}

		return normalizedTaskSet;
	}

	/**
	 * Finds the earliest release time of any remaining (unscheduled) task.
	 * 
	 * @return the release time found. If there are no remaining tasks, returns
	 *         {@link Long#MAX_VALUE}.
	 */
	protected long findEarliestReleaseTime() {
		return findNextReleaseTimeAfter(-1);
	}

	/**
	 * Finds the next release time of any remaining (unscheduled) task released
	 * after the current scheduling time.
	 * 
	 * @return the release time found. If there are no remaining tasks to be
	 *         released after the current scheduling time, returns
	 *         {@link Long#MAX_VALUE}.
	 */
	protected long findNextReleaseTime() {
		return findNextReleaseTimeAfter(currentTime);
	}

	/**
	 * Finds the next release time of any remaining (unscheduled) task released
	 * after the provided time.
	 * 
	 * @param afterTime
	 *            the time after which to search for tasks.
	 * @return the release time found. If there are no remaining tasks to be
	 *         released after the provided time, returns {@link Long#MAX_VALUE}.
	 */
	protected long findNextReleaseTimeAfter(long afterTime) {
		long earliestTime = Long.MAX_VALUE;
		for (Task task : remainingTasks) {
			long readyTime = task.getPhase();
			if (readyTime > afterTime && readyTime < earliestTime) {
				earliestTime = readyTime;
			}
		}
		return earliestTime;
	}

	/**
	 * Finds the next time after the current scheduling time when a processor
	 * (that is not already available at the current scheduling time) becomes
	 * available.
	 * 
	 * @return the processor availability time found.
	 */
	protected long findNextProcessorAvailabilityTime() {
		long earliestTime = Long.MAX_VALUE;
		for (LinkedList<Long> times : processorAvailabilityTimes.values()) {
			long time = times.getFirst();
			if (time > currentTime && time < earliestTime) {
				earliestTime = time;
			}
		}
		return earliestTime;
	}

	/**
	 * Chooses a processor that is available at the current scheduling time and
	 * is eligible to execute at least one ready task to be the current
	 * scheduling processor. If no processor fulfills both criteria, the current
	 * scheduling processor is set to {@code null}.
	 */
	protected void chooseProcessor() {
		currentProcessor = null;
		Set<String> usableProcessors = new HashSet<>();
		for (Task task : readyTasks) {
			if (task.getProcessorNames() == null) {
				usableProcessors.addAll(processors);
			} else {
				usableProcessors.addAll(task.getProcessorNames());
			}
		}

		for (Map.Entry<String, LinkedList<Long>> processorEntry : processorAvailabilityTimes
				.entrySet()) {
			if (usableProcessors.contains(processorEntry.getKey())
					&& processorEntry.getValue().getFirst() <= currentTime) {
				currentProcessor = processorEntry.getKey();
				break;
			}
		}
	}

	/**
	 * Chooses and returns a ready task that is eligible to be scheduled on the
	 * current scheduling processor.
	 * 
	 * Currently, the algorithm used simply chooses the eligible task with the
	 * earliest absolute deadline.
	 * 
	 * @return the chosen task. If no ready task is eligible to be scheduled on
	 *         the current scheduling processor, returns {@code null}.
	 */
	protected Task chooseTaskToSchedule() {
		Task earliestTask = null;
		for (Task task : readyTasks) {
			if ((task.getProcessorNames() == null || task.getProcessorNames()
					.contains(currentProcessor))
					&& (earliestTask == null || task.getPhase()
							+ task.getRelativeDeadline() < earliestTask
							.getPhase() + earliestTask.getRelativeDeadline())) {
				earliestTask = task;
			}
		}
		return earliestTask;
	}

	/**
	 * Attempts to make the provided task meet its deadline by removing
	 * previously scheduled tasks from the schedule so that the task can be
	 * scheduled at an earlier time.
	 * 
	 * This method does not validate whether the task meets its schedule either
	 * before or after its manipulations. This method may be called iteratively
	 * when its manipulations are unsuccessful.
	 * 
	 * Known issues and limitations with the current algorithm:
	 * <ul>
	 * <li>When the task to be scheduled specifies processor affinity with
	 * multiple processors, the algorithm will attempt to remove only tasks that
	 * were previously scheduled on the <em>current scheduling processor</em>;
	 * that is, it may not find feasible schedules that require moving the task
	 * to a different eligible processor.</li>
	 * <li>In order to avert potential infinite loops when two tasks are
	 * mutually unschedulable, the algorithm will abort its attempt to make a
	 * task meet its deadline and throw a {@link NoFeasibleScheduleException} if
	 * it encounters a previously scheduled task that does not either have a
	 * greater amount of slack time than the current task or have the ability to
	 * be scheduled on at least one processor on which the current task is not
	 * eligible to be scheduled. The algorithm therefore may not find some
	 * feasible schedules that would be found if the algorithm did not use this
	 * infinite loop avoidance strategy.</li>
	 * <li>Although the above strategy has been found to avoid the majority of
	 * infinite loops in practice, when used iteratively, the algorithm has the
	 * potential to enter an infinite loop in the rare case where two jobs, both
	 * of which have processor affinity with multiple processors, share only a
	 * portion of those processors. For example, if job 0 can be run on
	 * processors A and B, and job 1 can be run on processors B and C, the the
	 * algorithm <em>may</em> enter an infinite loop if the two jobs are
	 * mutually unschedulable on processor B.</li>
	 * </ul>
	 * 
	 * @param nextTask
	 *            the task being scheduled that has failed to meet its deadline.
	 * @throws NoFeasibleScheduleException
	 *             when the algorithm is unable to find a previously scheduled
	 *             task that can be removed from the schedule in order to allow
	 *             the current task to be scheduled at an earlier time, or when
	 *             the previously scheduled task that is found does not either
	 *             have a greater amount of slack time than the current task or
	 *             have the ability to be scheduled on at least one processor on
	 *             which the current task is not eligible to be scheduled.
	 */
	protected void attemptToMakeTaskMeetDeadline(Task nextTask)
			throws NoFeasibleScheduleException {
		Schedule.Entry lastEntry = (nextTask.getProcessorNames() == null ? schedule
				.removeLastEntry() : schedule.removeLastEntry(currentProcessor));
		if (lastEntry == null) {
			throw new NoFeasibleScheduleException("A task could "
					+ "not be completed before its deadline.");
		}
		Task lastTask = lastEntry.getTask();

		currentTime = Math.max(lastEntry.getStartTime(), nextTask.getPhase());
		if (!hasMoreSlack(lastTask, nextTask, currentTime)
				&& !canRunOnAdditionalProcessors(lastTask, nextTask)) {
			throw new NoFeasibleScheduleException("A task could "
					+ "not be completed before its deadline.");
		}

		remainingTasks.add(lastTask);
		currentProcessor = lastEntry.getProcessorName();
		processorAvailabilityTimes.get(currentProcessor).pop();
		if (firstReleaseTimes.get(currentProcessor) == lastEntry.getStartTime()) {
			firstReleaseTimes.remove(currentProcessor);
		}
		if (lastEntry.getStartTime() < rollbackTime) {
			rollbackTime = lastEntry.getStartTime();
		}
	}

	/**
	 * Determines if the provided task will meet its deadline if it is scheduled
	 * at the provided start time.
	 * 
	 * @param task
	 *            the {@link Task}.
	 * @param startTime
	 *            the proposed start time.
	 * @return {@code true} if the task finishes before or at its deadline when
	 *         it starts at the provided start time; {@code false} otherwise.
	 */
	protected boolean meetsDeadline(Task task, long startTime) {
		return startTime + task.getExecutionTime() <= task.getPhase()
				+ task.getRelativeDeadline();
	}

	/**
	 * Determines if the provided old task has more slack time than the provided
	 * new task at the provided start time.
	 * 
	 * @param oldTask
	 *            the old task.
	 * @param newTask
	 *            the new task.
	 * @param startTime
	 *            the start time at which to calculate the slack time for the
	 *            two tasks.
	 * @return {@code true} if the old task has more slack than the new task at
	 *         the provided start time; {@code false} otherwise.
	 */
	protected boolean hasMoreSlack(Task oldTask, Task newTask, long startTime) {
		long oldSlack = (oldTask.getPhase() + oldTask.getRelativeDeadline())
				- (startTime + oldTask.getExecutionTime());
		long newSlack = (newTask.getPhase() + newTask.getRelativeDeadline())
				- (startTime + newTask.getExecutionTime());
		return oldSlack > newSlack;
	}

	/**
	 * Determines if the provided old task is eligible to be scheduled on at
	 * least one processor on which the provided new task is not eligible to be
	 * scheduled.
	 * 
	 * @param oldTask
	 *            the old task.
	 * @param newTask
	 *            the new task.
	 * @return {@code true} if the old task is eligible to be scheduled on at
	 *         least one processor on which the provided new task is not
	 *         eligible to be scheduled; {@code false} otherwise.
	 */
	protected boolean canRunOnAdditionalProcessors(Task oldTask, Task newTask) {
		if (newTask.getProcessorNames() == null) {
			return false;
		}
		if (oldTask.getProcessorNames() == null) {
			return true;
		}
		if (newTask.getProcessorNames()
				.containsAll(oldTask.getProcessorNames())) {
			return false;
		}
		return true;
	}

}
